package com.share.algorithm.sort;

import java.util.Arrays;

/**
 * @desc: 归并排序
 *  先拆分-> 排序 -> 合并
 * @author:caifan
 * @date:2020/9/24
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arrays = {12, 4, 8, 7, 2, 10, 6, 9, 3, 5};
        mergeSort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 递归先拆分直至拆分节点为1然后排序，最后合并排序
     * @param arrays
     * @param left
     * @param right
     */
    public static void mergeSort(int[] arrays, int left, int right) {
        if (left < right) {//相等了则表示只有一个数据了不用拆了
            int mid = (left + right) / 2;
            // 拆左边
            mergeSort(arrays, left, mid);
            // 拆右边
            mergeSort(arrays, mid + 1, right);
            // 拆完之后进行合并排序
            merge(arrays, left, mid, right);
        }
    }

    public static void merge(int[] data, int left, int mid, int right) {
        int[] temp = new int[data.length];// 定义一个临时数组用来保存合并的数据

        int point1 = left;//左边第一个数的位置
        int point2 = mid + 1;// 右边第一个数的位置

        int loc = left; //当前所在位置
        while(point1 <= mid && point2 <= right) {
            if (data[point1] < data[point2]) {
                temp[loc] = data[point1];
                point1++;
                loc++;
            } else {
                temp[loc] = data[point2];
                point2++;
                loc++;
            }
        }

        while (point1 <= mid) {
            temp[loc++] = data[point1++];
        }
        while (point2 <= right) {
            temp[loc++] = data[point2++];
        }
        for (int i = left; i <= right; i++) {
            data[i] = temp[i];
        }
    }
}
